# 二叉树的中序遍历： https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        """
            递归解法， 和前序遍历一样，两种写法都行
        """

        if not root: return []

        rst = []
        def inorder(node: TreeNode) -> None:
            # 左
            if node.left:
                inorder(node.left)
            # 根
            rst.append(node.val)
            # 右
            if node.right:
                inorder(node.right)        

        inorder(root)
        return rst


    
    def inorderTraversal1(self, root: TreeNode) -> List[int]:
        """
            递归解法， 第二种写法，指出递归终止条件
        """
        if not root: return []

        rst = []
        def inorder(node: TreeNode) -> None:
            if not node: return 

            # 左
            inorder(node.left)
            # 根
            rst.append(node.val)
            # 右
            inorder(node.right)        

        inorder(root)
        return rst


    def inorderTraversal2(self, root: TreeNode) -> List[int]:
        """
            显示栈
        """

        rst = []
        cur = root
        stack = list()
        while cur or stack:
            # 1. 先一直找到当前节点的最左子节点
            while cur:
                stack.append(cur)
                cur = cur.left
            
            # 2. 最左已经加入到栈中， 取栈顶（最左元素），加入结果集
            node = stack.pop()
            rst.append(node.val)

            # 3. 该最左节点可能还存在右子树， 左，根， 右. 
            cur = node.right
            # 持续这个循环

        return rst

        
    # 还有一种终极方法，时间复杂度不变， 空间复杂度降低为 O(1)，改良显示栈的方法
    # Morris 中序遍历
